package com.example.demo.程序员面试金典;

/**
 * @description: TODO
 * @author: zhangzc
 * @modified By: zhangzc
 * @date: Created in 2022/9/8 14:44
 * @version:v1.0
 */
public class 魔术索引 {

	class Solution {
		public int findMagicIndex(int[] nums) {
			int left = 0, right = nums.length - 1;
			return find(nums, left, right);
		}

		private int find(int[] nums, int left, int right) {
			if (left > right) {
				return -1;
			}
			int mid = (left + right) >> 1;
			int leftIndex = find(nums, left, mid - 1);
			if (leftIndex != -1) {
				return leftIndex;
			}
			if (nums[mid] == mid) {
				return mid;
			}
			return find(nums, mid + 1, right);
		}
	}

	public int findMagicIndex(int[] nums) {
		for(int i=0;i<nums.length; ){
			if(nums[i]==i)
				return i;
			i=Math.max(nums[i],i+1);
		}
		return -1;
	}


}
